// 712. 两个字符串的最小ASCII删除和
// 给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。
/**
 * @param {string} s1
 * @param {string} s2
 * @return {number}
 */
var minimumDeleteSum = function (s1, s2) {
  const len1 = s1.length
  const len2 = s2.length
  const dp = new Array(len1 + 1).fill(0).map(() => new Array(len2 + 1).fill(0))
  const codeAt = (s, idx) => parseInt(s.charCodeAt(idx), 10)

  for (let i = 0; i <= len2; i++) {
    let ans = 0
    for (let k = 1; k <= i; k++) {
      ans += codeAt(s2, k - 1)
    }
    dp[0][i] = ans
  }
  for (let i = 0; i <= len1; i++) {
    let ans = 0
    for (let k = 1; k <= i; k++) {
      ans += codeAt(s1, k - 1)
    }
    dp[i][0] = ans
  }

  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      let p1 = Infinity
      // s1[i] 和 s2[j] 同时删除
      if (s1[i - 1] === s2[j - 1]) {
        p1 = dp[i - 1][j - 1]
      }
      // s1[i] 删除
      let p2 = dp[i - 1][j] + codeAt(s1, i - 1)
      // s2[j] 删除
      let p3 = dp[i][j - 1] + codeAt(s2, j - 1)

      dp[i][j] = Math.min(p1, p2, p3)
    }
  }

  return dp[len1][len2]
}

console.log(
  minimumDeleteSum(
    'delete',
    'leet'
  )
)
